package com.jn.algorithm.day027.question1248;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author 江南大学1033190417
 * @date 2023/1/2 21:32
 */
/*
给你一个整数数nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中 「优美子数组」 的数目。


 */
public class Solution {
    //显然超时
    public int numberOfSubarrays(int[] nums, int k) {
        int res = 0;
        for (int l = k; l <= nums.length; l++) {
            for (int i = 0; i <= nums.length - l; i++) {
                int num = 0;
                for (int j = i; j < i + l; j++) {
                    if (nums[j] % 2 == 1)
                        num++;
                }
                if (num == k)
                    res++;
            }
        }

        return res;
    }

    public int numberOfSubarrays2(int[] nums, int k) {
        int res = 0;
        int left = 0, right = 0, count = 0;
        while (right < nums.length) {
            if (nums[right++] % 2 == 1) {
                count++;
            }
            if (count == k) {
                //找left和right区间左边第一个奇数左边偶数的个数
                int leftCounts = 0;
                while (nums[left] % 2 == 0) {
                    leftCounts++;
                    left++;
                }
                //扩展区间右边，直到遇到奇数或者越界
                int temp = right;
                while (right < nums.length && nums[right] % 2 == 0) {
                    right++;
                }
                int rightCount = right - temp;
                res += (leftCounts + 1) * (rightCount + 1);
                left++;
                count--;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 2, 1, 1};

        Solution solution = new Solution();
        System.out.println(solution.numberOfSubarrays2(nums, 3));
    }
}
